package WhiteSpaceReport;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.ListIterator;

import DataModel.CommonLibrary.CGeometricOperations;
import DataModel.CommonLibrary.CommonDefs;
import DataModel.LayoutManager.CEdge;
import DataModel.LayoutManager.CRectangle;
import ScanLineAlghorithms.ScanLineFunctions;
/**
 * This class implements white space related operations.
 * @author Guy
 *
 */
public class WhiteSpaceByRect { 
	/**
	 * Implemenatation of of calculation of empty spaces in given area
	 * @param area area where to find empty spaces
	 * @param recsInArea rectangles residing in this area
	 * @param dir sweep direction
	 * @return rectangles representing empty areas
	 */
	public static LinkedList<CRectangle> findWhiteSpaceByRect (CRectangle area,LinkedList<CRectangle> recsInArea , char dir) 
	{
		LinkedList<CRectangle> freeArea = new LinkedList<CRectangle>();
		Hashtable<Long, LinkedList<CEdge>> scale = null;
		long startPoint = 0;
		long termPoint = 0;
		long scanStart = 0;
		long scanEnd = 0;
		if (dir == 'x') {
			scale = ScanLineFunctions.initEndpoints(recsInArea , 'y');
			startPoint = area.getBottomEdge().getStartPoint().y;
			termPoint = area.getTopEdge().getStartPoint().y;
			scanStart = area.getLeftEdge().getStartPoint().x;
			scanEnd = area.getRightEdge().getStartPoint().x;
		} else {
			scale = ScanLineFunctions.initEndpoints(recsInArea , 'x');
			startPoint = area.getLeftEdge().getStartPoint().x;
			termPoint = area.getRightEdge().getStartPoint().x;
			scanStart = area.getBottomEdge().getStartPoint().y;
			scanEnd = area.getTopEdge().getStartPoint().y;
			
		}
		LinkedList<Long> endpoints = new LinkedList<Long>(scale.keySet());
		
		if (!endpoints.contains(startPoint)) {
			endpoints.add(startPoint);
		}
		if (!endpoints.contains(termPoint)) {
			endpoints.add(termPoint);
		}
		Collections.sort(endpoints);
		
		ListIterator itPoints  = endpoints.listIterator();
		
		long curP2 = ((Long)itPoints.next()).longValue();
		long curP1 = -1;
		while (itPoints.hasNext()) {
			curP1 = curP2;
			curP2 = ((Long)itPoints.next()).longValue();
			if (curP1<startPoint || curP1==curP2) continue;
			if (curP1>=termPoint) break;
			
			LinkedList<CRectangle> curRects = null;
			Hashtable<Long, LinkedList<CEdge>> scanScale = null;
			if (dir == 'y') {
				curRects = CGeometricOperations.RecsInVerticalArea(curP1, curP2, recsInArea);
				scanScale = ScanLineFunctions.initEndpoints(curRects , 'y');
			} else {
				curRects = CGeometricOperations.RecsInHorisontalArea(curP1, curP2, recsInArea);
				scanScale = ScanLineFunctions.initEndpoints(curRects , 'x');
			}
			getEmptyRecsInRange(scanScale,dir,freeArea,scanStart,scanEnd,curP1,curP2);

		}
		return freeArea;
	}
	
	private static void getEmptyRecsInRange(Hashtable<Long, LinkedList<CEdge>> scanScale, char dir, LinkedList<CRectangle> freeArea ,long startScan, long endScan, long freeRectLow, long freeRectHigh) {
		LinkedList<Long> keys = new LinkedList<Long>(scanScale.keySet());
		if (!keys.contains(startScan)) keys.add(startScan);
		if (!keys.contains(endScan)) keys.add(endScan);
		Collections.sort(keys);
		int counterPre =1;
		//free space indicator : if zero we are at free space
		int counter =0;
		long freeRectStart =0;
		long freeRectEnd = 0;
		ListIterator itKeys  = keys.listIterator();
		while (itKeys.hasNext()) {
			Long key = (Long)itKeys.next();

			LinkedList<CEdge> edges = scanScale.get(key);
			if (edges != null) {
				ListIterator itEdges = edges.listIterator();
				while (itEdges.hasNext()) {
					CEdge edge = (CEdge) itEdges.next();
					if (dir == 'x') {
						//rectangle ended
						if (edge.getEndPoint().y<=edge.getStartPoint().y) {

							counter--;
						}
						//rectangle started
						if (edge.getStartPoint().y<=edge.getEndPoint().y) {
							counter++;
						}
					}
					if (dir == 'y') {
						//rectangle ended
						if (edge.getEndPoint().x>=edge.getStartPoint().x) {
							counter--;
						}
						//rectangle started
						if (edge.getStartPoint().x>=edge.getEndPoint().x) {
							counter++;
						}
					}
				}
			}

//			start of free zone

			if (counterPre == 1 && counter == 0 ) {
				freeRectStart = key;
			} 
			//end of free zone
			else if (counterPre == 0 && counter == 1) {
				CRectangle rec = null;
				freeRectEnd = key;
				if (dir == 'x') rec = new CRectangle((int)freeRectStart,(int)freeRectLow,(int)freeRectEnd,(int)freeRectHigh,CommonDefs.Layer.None,-2);
				else
					rec = new CRectangle((int)freeRectLow,(int)freeRectStart,(int)freeRectHigh,(int)freeRectEnd,CommonDefs.Layer.None,-2);
				freeArea.add(rec);
			} 
			//end of freee zone
			else if (counter == 0 && key == endScan) {
				freeRectEnd = key;
				CRectangle rec = null;
				if (dir == 'x') rec = new CRectangle((int)freeRectStart,(int)freeRectLow,(int)freeRectEnd,(int)freeRectHigh,CommonDefs.Layer.None,-2);
				else
					rec = new CRectangle((int)freeRectLow,(int)freeRectStart,(int)freeRectHigh,(int)freeRectEnd,CommonDefs.Layer.None,-2);

				freeArea.add(rec);
			}
			counterPre = counter;	
		}
	}
	/**
	 * Implementation of finding minimal empty space that can include given rectangle
	 * @param inputRec rectangle we want to place
	 * @param area area in which we want to place
	 * @param recsInArea other rectangles residing in the area
	 * @return Rectangle which represents minimal empty space
	 */
	public static CRectangle findMinEnclosing(CRectangle inputRec, CRectangle area,LinkedList<CRectangle> recsInArea) {
		LinkedList<CRectangle> freeAreaByX =findWhiteSpaceByRect (area,recsInArea,  'x');
		LinkedList<CRectangle> freeAreaByY =findWhiteSpaceByRect (area,recsInArea,  'y');
		CRectangle minRecX=null;
		CRectangle minRecY=null;
		
		for (CRectangle rec : freeAreaByX) {
			if(CRectangle.recFits(inputRec, rec)) {
				if (minRecX == null ) minRecX = rec;
				else
				{
					if (rec.getArea()<minRecX.getArea()) minRecX = rec;
				}
			}
		}
		for (CRectangle rec : freeAreaByY) {
			if(CRectangle.recFits(inputRec, rec)) {
				if (minRecY == null ) minRecY = rec;
				else
				{
					if (rec.getArea()<minRecX.getArea()) minRecY = rec;
				}
			}
		}
		if (minRecX == null) return minRecY;
		if (minRecY == null) return minRecX;
		return minRecX.getArea()<minRecY.getArea() ? minRecX : minRecY;
	}
	

}
	

